﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_40_CombinationSum2
{
    class MainProkect
    {
        static void Main(string[] args)
        {
            //IList<IList<int>> list = CombinationSum2(new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, 27);
            IList<IList<int>> list = CombinationSum2(new int[] { 2, 5, 2, 1, 2 }, 5);
            foreach (var item1 in list)
            {
                foreach (var item in item1)
                {
                    Console.Write(item + " ");
                }
                Console.WriteLine();
            }
            Console.ReadKey();

        }
        public static IList<IList<int>> CombinationSum2(int[] candidates, int target)
        {

            #region 递归+回溯
            int len = candidates.Length;
            IList<IList<int>> res = new List<IList<int>>();
            if (len == 0) return res;
            int index = 0;
            Array.Sort(candidates);

            DFS(candidates, res, target, index, new List<int>());
            return res;
            #endregion

            #region 递归
            //转换树+递归
            //IList<IList<int>> list = new List<IList<int>>();

            //int sum = 0;
            //Array.Sort(candidates);

            //for (int i = 0; i < candidates.Length; i++)
            //{
            //    Tree(list, new List<int>(), sum, candidates, target, candidates[i], i);
            //}
            //return list;
            #endregion
        }

        public static void DFS(int[] candidates, IList<IList<int>> res, int target, int index, List<int> list)
        {
            if (target == 0)
            {
                res.Add(new List<int>(list));
                return;
            }

            for (int i = index; i < candidates.Length; i++)
            {
                //大剪枝(因为已经排过序了，所以后面都是小于零，可以直接break)
                if (target - candidates[i] < 0) break;

                //小剪枝
                if (i > index && candidates[i] == candidates[i - 1]) continue;

                list.Add(candidates[i]);
                target -= candidates[i];

                DFS(candidates, res, target, i + 1, list);

                target += candidates[i];
                list.Remove(candidates[i]);
            }
        }


        public static void Tree(IList<IList<int>> lists, List<int> list, int sum, int[] candidates, int target, int value, int index)
        {
            sum += value;
            list.Add(value);
            if (sum == target)
            {
                list.Sort();
                if (!IsRepeat(lists, list))
                {
                    lists.Add(list);
                }
            }
            else if (sum > target)
            {
                return;
            }
            else
            {
                index++;
                for (int i = index; i < candidates.Length; i++)
                {
                    List<int> s = new List<int>();
                    s.AddRange(list);
                    Tree(lists, s, sum, candidates, target, candidates[i], i);
                }
            }
        }
        public static bool IsRepeat(IList<IList<int>> list, IList<int> que)
        {
            bool res = false;
            foreach (var item in list)
            {
                if (item.Count == que.Count)
                {
                    res = true;
                    for (int i = 0; i < item.Count; i++)
                    {
                        if (item[i] != que[i])
                        {
                            res = false;
                        }
                    }
                    if (res)
                    {
                        return res;
                    }
                }
            }
            return res;
        }

    }
}
